//
// Created by LiuYou on 2021/11/28.
//

#include <iostream>
#include <vector>
#include <iterator>


/**
 * @brief 选择排序。
 * @param arr 要排序的数组。
 *
 * @details <p>选择排序开辟了多少额外空间?
 * int i = 0;
 * int j = i + 1;
 * int minIndex = i; 就这几个变量/对象。所以额外的空间复杂度是 1 。</p>
 *
 */
static void selectionSort(std::vector<int>& arr) {
    // 如果这个数组为空或者长度为1, 那么还需要什么排序。直接就是有序。
    if (arr.empty() || arr.size() < 2) {
        return;
    }

    // i ~ N-1
    // 我在 i 到 N-1 范围内选最小值, 并且把最小值放到 i 位置上去。
    // 例如: 一开始, 从 0 ~ N-1 上选最小值放到 0 位置上去;
    // 然后在 1 ~ N-1 上选最小值放到 1 位置上去。
    for (int i = 0; i < arr.size() - 1; ++i) {
        // 一开始我以为最小值的位置就是 i 位置。
        int minIndex = i;
        /* 然后 j 从 i+1 开始, 如果遇到的值比之前在 minIndex 位置的值还小的话,
         * 那么 就是 j 位置的值是最小值的位置。如果之后的所有的位置没有比之前的 minIndex 位置
         * 的值小的话, 那我 minIndex 就保持不变。*/
        for (int j = i + 1; j < arr.size(); ++j) {
            minIndex = arr[j] < arr[minIndex] ? j : minIndex;
        }
        // 通过 minIndex 和一个 for循环, 我找到了最小值的位置。然后交换。
        std::swap( arr[i], arr[minIndex] );
    }
}


static void test(std::vector<int>& arr) {
    selectionSort( arr );
}


int main(int argc, char** argv) {
    std::vector<int> arr{8, 2, 9, 100, 34, 9, 345, 902};
    // BubbleSort
    {
        test( arr );
        selectionSort( arr );
        std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, " " ));
        std::cout << std::endl;
    }

    std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, " " ));
    std::cout << std::endl;


    return 0;
}
